import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 牛孟俊
 * Date: 2023-11-10
 * Time: 11:16
 */
public class Test {
    //前K个高频词
    public List<String> topKFrequent(String[] words, int k) {
         //先建立小根堆
        Map<String,Integer> map = new HashMap<>();
        for (String s:
             words) {
            if(map.get(s) == null) {
                map.put(s,1);
            } else {
                //map当中已经有array[i]这个值了
                int val = map.get(s);
                map.put(s,val+1);
            }
        }
        //每个单词出现次数 已经统计完毕

        //建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    //根据字母顺序变成大根堆
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });//大小为K的小根堆

        //遍历 MAP,并且放入小根堆
        for(Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) == 0) {
                    //频率一样的情况下，判断k值，k小的入
                    if(top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                } else {
                    if(top.getValue().compareTo(entry.getValue()) < 0) {
                        //entry的value大
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        //循环走完了，已经找到了前k个元素了
        //需要将小根的元素拿出来放入到一个集合当中进行逆置。这样就是我们需要的元素了
        List<String> ret = new ArrayList<>();
        for(int i = 0; i < k; i++) {
            String s = minHeap.poll().getKey();
            ret.add(s);
        }
        //逆置
        Collections.reverse(ret);
        return ret;
    }


    /**
     * 统计每个数据出现的次数
     * K-V结构
     * @param array
     */
    public static void func2(int[] array) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < array.length; i++) {
            if(map.get(array[i]) == null) {
                map.put(array[i],1);
            } else {
                //map当中已经有array[i]这个值了
                int val = map.get(array[i]);
                map.put(array[i],val+1);
            }
        }
        System.out.println(map);

    }

    public static void main3(String[] args) {
        int[] array = {1,2,3,12,32,2,1,3,21};
        func2(array);
    }
    public static void func1(int[] array) {
        Set<Integer> set = new HashSet<>();
        for(int  i = 0; i < array.length; i++) {
            set.add(array[i]);
        }
        System.out.println(set);
    }

    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            if(!set.contains(nums[i])) {
                set.add(nums[i]);
            } else {
                set.remove(nums[i]);
            }
        }
        //Set当中只有出现一次的元素
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }

    //宝石与石头
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        int count = 0;
        //遍历宝石字符串，将宝石放入集合
        for(int i = 0; i < jewels.length(); i++) {
            set.add(jewels.charAt(i));
        }
        //遍历石头字符串
        for(int i = 0; i < stones.length(); i++) {
            if(set.contains(stones.charAt(i))) {
                count++;
            }
        }
        return count;
    }

    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case

            String str1 = in.nextLine();
            String str2 = in.nextLine();
            func(str1,str2);
        }

        //func("7_This_is_a_test","_hs_s_a_es");
    }

    /**
     *
     * @param str1 应该输入的（键盘打上去的）
     * @param str2 实际输入的（键盘上有的键坏掉了）
     */
    public static void func(String str1,String str2) {
        Set<Character> set = new HashSet<>();
        //以大写的形式放进去
        for(char ch : str2.toUpperCase().toCharArray()) {
            set.add(ch);//坏键盘输入的放到set集合当中
        }

        Set<Character> setBroken = new HashSet<>();
        for (char ch : str1.toUpperCase().toCharArray()) {
            //怀键盘当中没有的，并且当前的setBroken还没有，就放到setBroken
            if(!set.contains(ch) && !setBroken.contains(ch)) {
                setBroken.add(ch);
                System.out.print(ch);
            }
        }
    }
    public static void main1(String[] args) {
        int[] array = {1,2,3,4,3,1,2,2};
        func1(array);
    }
}
